package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class CombinationSumIii{
    public static void main(String[] args) {
         
         Solution solution = new CombinationSumIii().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backTrack(k,n,1,0,new ArrayList<>());
        return result;
    }

        private void backTrack(int k, int n, int step, int sum, ArrayList<Object> path) {
            if (sum == n && path.size() == k){
                result.add(new ArrayList(path));
                return;
            }
            if (sum > n || path.size() > k || step > 9){
                return;
            }
            backTrack(k,n,step+1,sum,path);
            path.add(step);
            backTrack(k,n ,step+1,sum+step,path);
            path.remove(path.size()-1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}